\input{euler.tex}

\begin{document}

\problem[144]{Multiple Reflections of a Laser Beam}

In laser physics, a \emph{white cell} is a mirror system that acts as a delay line for the laser beam. The beam enters the cell, bounces around on the mirrors, and eventually works its way back out.

The specific white cell we will be considering is an ellipse with the equation $4 x^2 + y^2 = 100$.

The section corresponding to $-0.01 \le x \le +0.01$ at the top is missing, allowing the light to enter and exit through the hole.

The light beam in this problem starts at the point $(0.0, 10.1)$ just outside the white cell, and the beam first impacts the mirror at $(1.4, -9.6)$.
 
Each time the laser beam hits the surface of the ellipse, it follows the usual law of reflection: angle of incidence equals angle of reflection. That is, both the incident and reflected beams make the same angle with the normal line at the point of incidence.

How many times does the beam hit the internal surface of the white cell before it exits?

\solution

We compute each incidence point in turn until the beam exits the cell. Let $P_0$ be the source of the beam and $P_1$ be the incidence point. To compute the next incidence point $P_2$, we first find the normal line $l$ of the ellipse at $P_1$, mirror $P_0$ against $l$ to get $P'_0$, and then intercept line $P_1 P'_0$ with the ellipse at $P_2$.

Below are a few results in analytic geometry are necessary for the computation.

To find the normal line at point $P(x_0,y_0)$ of an ellipse with diameters $a$ and $b$, we write the parametric equation of the ellipse 
\begin{align}
x &= a \cos \theta \notag \\
y &= b \sin \theta , \notag
\end{align}
and note that 
\begin{align}
dx &= -a \sin \theta d\theta \notag \\
dy &= b \cos \theta d\theta . \notag
\end{align}
It follows that the slope of the normal line is $-dx/dy = (a^2 y_0) / (b^2 x_0)$.

To find the mirror point of a point $P_1(x_1,y_1)$ against a line, we describe the line by its parametric equation
\begin{align}
x &= x_0 + pt \notag \\
y &= y_0 + qt \notag .
\end{align}
Next, we find a point $P(x,y)$ on the line such that $P_1 P$ is perpendicular to the line. This is as easy as solving the following vector inner product
\[
(x-x_1)(x-x_0) + (y-y_1)(y-y_0) = 0 .
\]
Once we find this point $P$, we can mirror $P_1$ against $P$ to find its mirror against the line.

To intersect a line with an ellipse, we describe the line by its parametric equation and the ellipse by its standard equation
\[
\frac{x^2}{a^2} + \frac{y^2}{b^2} = 1 .
\]
Substituting the line equation into the ellipse equation and rearranging terms, we get
\[
(b^2 p^2 + a^2 q^2) t^2 + 2(b^2 p x_0 + a^2 q y_0) t + (b^2 x_0^2 + a^2 y_0^2 - a^2 b^2) = 0 .
\]
This equation can be easily solved. In addition, we define the \emph{direction} of the line to be the direction where $t$ increases. Thus, we can easily distinguish the two intersection points (where they exist) by calling the point corresponding to the smaller solution of $t$ the \emph{near point}, and the point corresponding to the greater solution of $t$ the \emph{far point}.

In the special case where $(x_0, y_0)$ is on the ellipse (as in this problem), the constant term in the above equation would vanish, making it a linear equation and thus readily solved.

\answer

354

\complexity

Let $n$ be the number of reflections before the beam exits the white cell.

Time complexity: $\BigO(n)$

Space complexity: $\BigO(1)$

\end{document} 